package 排列硬币;

/**
 * 排列硬币：
 * 总共有n枚硬币，将它们摆成一个阶梯形状，第k行就必须正好有k枚硬币。
 * 给定一个数字n，找出可形成完整阶梯行的总行数。
 * n是一个非负整数，并且在32位有符号整形的范围内。
 * <p>
 * 暴力递归
 * 去重递归
 * 双指针迭代
 */
public class Solution {
    public static void main(String[] args) {
        int v = arrangeCoins(100);
        System.out.println("v = " + v);

        v = arrangeCoins2(100);
        System.out.println("v = " + v);

        v = arrangeCoins3(100);
        System.out.println("v = " + v);

    }

    /**
     * 迭代法
     */
    public static int arrangeCoins(int n) {
        for (int i = 1; i <= n; i++) {
            n = n - i;
            if (n <= i) {
                return i;
            }
        }
        return 0;
    }

    /**
     * 二分法
     */
    public static int arrangeCoins2(int n) {
        int l = 0, h = n;
        while (l <= h) {
            int mid = l + (h - l) / 2;
            int cost = ((mid + 1) * mid) / 2;
            if (n == cost) {
                return mid;
            }
            if (cost > n) {
                h = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return h;
    }


    /**
     * 牛顿迭代
     */
    public static int arrangeCoins3(int n) {
        if (n == 0) {
            return n;
        }
        return (int) sqrt(n, n);
    }

    public static double sqrt(double x, double n) {
        double res = (x + (2 * n - x) / x) / 2;
        if (res == x) {
            return x;
        }
        return sqrt(res, n);
    }
}
